package com.person.leetcode.editor.cn;

/**
 * 62.不同路径
 * 2022-11-11 11:42:30
 **/
public class Sequence_0062_UniquePaths {
    public static void main(String[] args) {
        Solution solution = new Sequence_0062_UniquePaths().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
//        private int flag = 0;
//
//        public int uniquePaths(int m, int n) {
//            long ans = 1;
//            for (int x = 1; x < m; x++) {
//                ans = ans * ((n+x-1)/x);//精度损失
//                ans = ans * (n+x-1)/x;
//            }
//            return (int)ans;
//        }

        public int uniquePaths(int m, int n) {
            long ans = 1;
            for (int x = n, y = 1; y < m; ++x, ++y) {
                ans = ans * x / y;// 2/1 3/2
            }
            return (int) ans;
        }

//
//
//        //暴力法
//        private void travel(int x, int y, int m, int n) {
//            if (x > m || y > n) {
//                return;
//            }
//            if (x == m && y == n) {
//                flag++;
//            }
//            travel(x + 1, y, m, n);
//            travel(x, y + 1, m, n);
//        }
    }

//leetcode submit region end(Prohibit modification and deletion)

}